Системное программирование

Тема 4. Организация параллельной обработки с использованием средств исключения и предупреждения состязаний

Системное программирование

План лекции

1. Состояние процессов

2. Описание процессов

3. Взаимодействие процессов

4. Задача взаимного исключения

5. Решение задачи взаимного исключения

6. Задача «производители-потребители» и её решения

7. Классические задачи синхронизации

Организация параллельной обработки
Системное программирование

1. Состояния процессов

1.1. Диаграмма состояний процесса

Организация параллельной обработки
Системное программирование

1.2. Описание состояний

Состояния процесса:

Состояние Описание
Новый (New) Создан, но не готов к выполнению
Готовый (Ready) Ожидает выделения процессора
Выполняется (Running) Инструкции выполняются
Ожидание (Waiting) Ожидает события или ресурса
Завершение (Terminated) Выполнение завершено

Переходы:

  • Admit — планировщик принимает процесс
  • Dispatch — выделение процессора
  • Interrupt/Timeout — истечение кванта времени
  • Wait/Event — ожидание/наступление события
Организация параллельной обработки
Системное программирование

2. Описание процессов

2.1. Блок управления процессом (PCB)

Process Control Block — структура данных ядра, содержащая информацию о процессе.

struct task_struct {  // Linux
    pid_t pid;              // Идентификатор
    pid_t ppid;             // Родительский PID
    volatile long state;    // Состояние
    struct mm_struct *mm;   // Адресное пространство
    struct files_struct *files;  // Открытые файлы
    struct signal_struct *signal; // Сигналы
    struct list_head tasks; // Список задач
    cputime_t utime, stime; // Время CPU
    // ...
};
Организация параллельной обработки
Системное программирование

2.2. Содержимое PCB

Категории информации:

Идентификация:

  • PID, PPID
  • UID, GID
  • Имя процесса

Состояние:

  • Текущее состояние
  • Программный счетчик
  • Регистры
  • Флаги процессора

Управление памятью:

  • Таблицы страниц
  • Сегменты кода/данных/стека
  • Разделяемая память

Управление ресурсами:

  • Открытые файлы
  • Сигналы
  • IPC объекты
Организация параллельной обработки
Системное программирование

2.3. Контекст процесса

Контекст — совокупность данных, необходимых для возобновления выполнения процесса.

Компоненты контекста:

Переключение контекста — сохранение контекста текущего процесса и загрузка контекста нового.

Организация параллельной обработки
Системное программирование

3. Взаимодействие процессов

3.1. Модели взаимодействия

Независимые процессы:

  • Не разделяют данные
  • Не влияют друг на друга
  • Планировщик изолирует

Взаимодействующие процессы:

  • Разделяют данные
  • Обмениваются информацией
  • Требуют синхронизации

Механизмы IPC (Inter-Process Communication):

  • Разделяемая память
  • Передача сообщений
  • Сигналы
  • Файлы
  • Сокеты
Организация параллельной обработки
Системное программирование

3.2. Разделяемая память

Shared Memory — сегмент памяти, доступный нескольким процессам.

Windows:

// Создание
HANDLE hMap = CreateFileMapping(
    INVALID_HANDLE_VALUE,
    NULL, PAGE_READWRITE,
    0, 4096, L"MySharedMem"
);

// Отображение
void* pMem = MapViewOfFile(
    hMap, FILE_MAP_ALL_ACCESS,
    0, 0, 4096
);

// Использование
strcpy((char*)pMem, "Hello");

// Освобождение
UnmapViewOfFile(pMem);
CloseHandle(hMap);
Организация параллельной обработки
Системное программирование

3.3. Разделяемая память в POSIX

#include <sys/shm.h>

// Создание
int shmid = shmget(
    IPC_PRIVATE,    // Ключ
    4096,           // Размер
    IPC_CREAT | 0666
);

// Присоединение
void* addr = shmat(shmid, NULL, 0);

// Использование
sprintf((char*)addr, "Shared data");

// Отсоединение
shmdt(addr);

// Удаление
shmctl(shmid, IPC_RMID, NULL);
Организация параллельной обработки
Системное программирование

4. Задача взаимного исключения

4.1. Постановка задачи

Условия критической секции:

  1. Взаимное исключение — если процесс в критической секции, другие не могут входить
  2. Прогресс — если никто не в секции и есть желающие, выбор следующего не может откладываться бесконечно
  3. Ограниченное ожидание — процесс не должен ждать входа бесконечно долго

Пример критической секции:

// Процесс 1          // Процесс 2
while (true) {        while (true) {
    // Вход              // Вход
    counter++;          counter++;
    // Выход             // Выход
}                     }
Организация параллельной обработки
Системное программирование

4.2. Неправильные решения

Решение 1: Флаг занятости

// Процесс 0          // Процесс 1
while (flag[1]);      while (flag[0]);
flag[0] = true;       flag[1] = true;
// Крит. секция       // Крит. секция
flag[0] = false;      flag[1] = false;

❌ Нарушает взаимное исключение (одновременный вход)

Решение 2: Строгое чередование

// Процесс 0          // Процесс 1
while (turn != 0);    while (turn != 1);
// Крит. секция       // Крит. секция
turn = 1;             turn = 0;

❌ Нарушает прогресс (обязательное чередование)

Организация параллельной обработки
Системное программирование

5. Решение задачи взаимного исключения

5.1. Алгоритм Петерсона

Корректное программное решение:

// Общие переменные
int turn;
bool flag[2] = {false, false};

// Процесс i (i = 0 или 1)
void process(int i) {
    int j = 1 - i;
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ; // Ожидание
    
    // Критическая секция
    
    flag[i] = false;
}

Удовлетворяет всем трем условиям

Организация параллельной обработки
Системное программирование

5.2. Аппаратные решения

Запрет прерываний:

cli();      // Clear Interrupts
// Критическая секция
sti();      // Set Interrupts

❌ Не работает на многопроцессорных системах

Атомарные инструкции:

// Test-And-Set
bool test_and_set(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

// Использование
while (test_and_set(&lock))
    ; // Ожидание
// Критическая секция
lock = false;
Организация параллельной обработки
Системное программирование

5.3. Мьютексы и семафоры

Мьютекс:

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&mutex);
// Критическая секция
pthread_mutex_unlock(&mutex);

Семафор:

sem_t sem;
sem_init(&sem, 0, 1);  // Бинарный семафор

sem_wait(&sem);     // P()
// Критическая секция
sem_post(&sem);     // V()
Организация параллельной обработки
Системное программирование

6. Задача «производители-потребители»

6.1. Постановка задачи

Условия:

  • Один или несколько производителей генерируют данные
  • Один или несколько потребителей обрабатывают данные
  • Общий буфер ограниченного размера
  • Производитель ждет при полном буфере
  • Потребитель ждет при пустом буфере

Организация параллельной обработки
Системное программирование

6.2. Неправильное решение

// Общие переменные
int count = 0;

// Производитель
void produce() {
    while (count == N)
        ; // Ожидание
    buffer[in] = item;
    in = (in + 1) % N;
    count++;
}

// Потребитель
void consume() {
    while (count == 0)
        ; // Ожидание
    item = buffer[out];
    out = (out + 1) % N;
    count--;
}

❌ Состояние гонки при доступе к count!

Организация параллельной обработки
Системное программирование

6.3. Решение с семафорами

semaphore mutex = 1;      // Взаимное исключение
semaphore empty = N;      // Число пустых ячеек
semaphore full = 0;       // Число заполненных ячеек

// Производитель
void producer() {
    while (true) {
        item = produce_item();
        sem_wait(&empty);   // Ждать пустую ячейку
        sem_wait(&mutex);   // Войти в крит. секцию
        buffer[in] = item;
        in = (in + 1) % N;
        sem_post(&mutex);   // Выйти из крит. секцию
        sem_post(&full);    // Увеличить счетчик полных
    }
}

// Потребитель
void consumer() {
    while (true) {
        sem_wait(&full);    // Ждать заполненную ячейку
        sem_wait(&mutex);   // Войти в крит. секцию
        item = buffer[out];
        out = (out + 1) % N;
        sem_post(&mutex);   // Выйти из крит. секцию
        sem_post(&empty);   // Увеличить счетчик пустых
        consume_item(item);
    }
}
Организация параллельной обработки
Системное программирование

6.4. Решение с мониторами

Монитор — высокоуровневая абстракция синхронизации.

monitor ProducerConsumer {
    int buffer[N];
    int count = 0, in = 0, out = 0;
    condition notFull, notEmpty;
    
    void produce(int item) {
        if (count == N)
            notFull.wait();
        buffer[in] = item;
        in = (in + 1) % N;
        count++;
        notEmpty.signal();
    }
    
    int consume() {
        if (count == 0)
            notEmpty.wait();
        int item = buffer[out];
        out = (out + 1) % N;
        count--;
        notFull.signal();
        return item;
    }
}
Организация параллельной обработки
Системное программирование

7. Классические задачи синхронизации

7.1. Задача «читатели-писатели»

Условия:

  • Несколько читателей могут читать данные одновременно
  • Только один писатель может писать в данный момент
  • Писатель не может писать, пока есть читатели

Решение с приоритетом читателей:

#include <pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t wrt = PTHREAD_MUTEX_INITIALIZER;
int readcount = 0;

void reader() {
    pthread_mutex_lock(&mutex);
    readcount++;
    if (readcount == 1)
        pthread_mutex_lock(&wrt);
    pthread_mutex_unlock(&mutex);

    pthread_mutex_lock(&mutex);
    readcount--;
    if (readcount == 0)
        pthread_mutex_unlock(&wrt);
    pthread_mutex_unlock(&mutex);
}

void writer() {
    pthread_mutex_lock(&wrt);

    pthread_mutex_unlock(&wrt);
}
Организация параллельной обработки
Системное программирование

7.2. Задача «обедающие философы»

Условия:

  • 5 философов сидят за круглым столом
  • Между каждыми двумя — одна вилка (всего 5)
  • Для еды философу нужны две вилки (левая и правая)
  • Не должно быть дедлока и голодания

Наивное решение (риск дедлока):

pthread_mutex_t forks[5];

void philosopher(int i) {
    pthread_mutex_lock(&forks[i]);
    pthread_mutex_lock(&forks[(i + 1) % 5]);

    pthread_mutex_unlock(&forks[(i + 1) % 5]);
    pthread_mutex_unlock(&forks[i]);
}

❌ Если все философы одновременно возьмут левую вилку — дедлок

Решение: иерархия ресурсов

void philosopher(int i) {
    int first = min(i, (i + 1) % 5);
    int second = max(i, (i + 1) % 5);

    pthread_mutex_lock(&forks[first]);
    pthread_mutex_lock(&forks[second]);

    pthread_mutex_unlock(&forks[second]);
    pthread_mutex_unlock(&forks[first]);
}

✅ Философ всегда берёт вилку с меньшим номером первой — цикл невозможен

Организация параллельной обработки
Системное программирование

7.3. Задача «спящий парикмахер»

Условия:

  • Парикмахер стрижет одного клиента, остальные ждут в зале (N стульев)
  • Если клиентов нет — парикмахер спит
  • Если все стулья заняты — клиент уходит

Решение с семафорами:

#include <semaphore.h>
#include <pthread.h>

#define CHAIRS 5

sem_t customers;
sem_t barber;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int waiting = 0;

void *barber_thread(void *arg) {
    while (1) {
        sem_wait(&customers);

        pthread_mutex_lock(&mutex);
        waiting--;
        sem_post(&barber);
        pthread_mutex_unlock(&mutex);

    }
}

void *customer_thread(void *arg) {
    pthread_mutex_lock(&mutex);
    if (waiting < CHAIRS) {
        waiting++;
        sem_post(&customers);
        sem_post(&barber);
        pthread_mutex_unlock(&mutex);

    } else {
        pthread_mutex_unlock(&mutex);

    }
    return NULL;
}
Организация параллельной обработки
Системное программирование

Резюме

Ключевые моменты лекции:

  1. Состояния процесса — модель жизненного цикла
  2. PCB — структура данных для управления процессом
  3. IPC — механизмы взаимодействия процессов
  4. Взаимное исключение — три условия корректности
  5. Алгоритм Петерсона — программное решение
  6. Производители-потребители — классическая задача синхронизации
  7. Читатели-писатели — приоритет доступа к разделяемым данным
  8. Обедающие философы — предотвращение дедлока через иерархию ресурсов
  9. Спящий парикмахер — координация с ограниченным буфером ожидания
Организация параллельной обработки
Системное программирование

Вопросы для самопроверки

  1. Какие состояния может иметь процесс?
  2. Что содержится в блоке управления процессом?
  3. Какие условия должны выполняться для взаимного исключения?
  4. Как работает алгоритм Петерсона?
  5. Как решить задачу производителей-потребителей с помощью семафоров?
  6. Что такое монитор?
Организация параллельной обработки
Системное программирование

Практические задания

Самостоятельная работа (8 часов):

  1. Реализовать алгоритм Петерсона на C
  2. Написать программу с разделяемой памятью (Windows/Linux)
  3. Решить задачу производителей-потребителей с семафорами
  4. Исследовать состояние гонки на примере счётчика
Организация параллельной обработки
Системное программирование

Рекомендуемая литература

Основная:

  1. Таненбаум, Э. Современные операционные системы. — 4-е изд. — СПб.: Питер, 2021.
  2. Силвершатц, А. Операционные системы. Концепции и технологии. — СПб.: БХВ-Петербург, 2014.
  3. Kerrisk, M. The Linux Programming Interface. — No Starch Press, 2010.

Дополнительная:

  1. Дейкстра, Э. Взаимное исключение в мультипрограммировании.
  2. man pages: shm_overview(7), sem_overview(7), pthreads(7)
  3. The Little Book of Semaphores (Downey, A.)
Организация параллельной обработки

Кратко пробежаться по плану, отметить, что тема связана с предыдущими лекциями о процессах и планировании. Указать, что основное внимание — на проблемах синхронизации и состязаний. Практическое использование API объектов синхронизации (CreateMutex, CreateSemaphore, pthread_mutex) рассмотрено в лекции 3.

Нарисовать диаграмму на доске параллельно. Спросить студентов, какие ещё состояния возможны (например, зомби-состояние в Linux). Обратить внимание на переход timeout — это основа вытесняющего планирования.

Задать вопрос: «Может ли процесс перейти из состояния "Ожидание" сразу в "Выполняется"?» Ответ — да, если ресурс освободился и процессор свободен. Напомнить про различие между блокирующим и неблокирующим I/O.

Обратить внимание на ключевое слово volatile перед state — объяснить, почему оно здесь нужно (значение может меняться из другого контекста). Предложить студентам выполнить `cat /proc/<pid>/status` на практике и найти соответствующие поля.

Задать вопрос: «Почему программный счетчик и регистры хранятся именно в PCB, а не где-то ещё?» Подчеркнуть связь PCB с переключением контекста — эти данные нужны, чтобы корректно возобновить процесс. Упомянуть, что в Linux task_struct содержит ~400 полей.

Подчеркнуть, что переключение контекста — дорогая операция (сотни тактов), поэтому ядро старается минимизировать его частоту. Типичная ошибка студентов: путать контекст процесса с контекстом потока. Упомянуть системный вызов getcontext/setcontext из POSIX.

Спросить: «Приведите примеры независимых и взаимодействующих процессов из повседневного опыта». Ключевой переход: от независимых процессов к разделяемым данным и проблеме состязаний. Перечислить IPC — кратко, подробно каждый механизм будет в следующем разделе.

Обратить внимание на двухэтапную схему: сначала создаём объект (CreateFileMapping), затем отображаем в адресное пространство (MapViewOfFile). Важный момент: по имени "MySharedMem" другой процесс может открыть ту же память. Предупредить об ошибке: забывают вызвать UnmapViewOfFile — утечка адресного пространства.

Показать параллель между Windows и POSIX API. Объяснить разницу между IPC_PRIVATE и именованным ключом (ftok). Частая ошибка: не удаляют разделяемую память через shmctl — она остаётся в системе до перезагрузки. Показать команду ipcs для просмотра.

Ключевой слайд лекции. Три условия Дейкстры нужно выписать на доску и разобрать каждое. Спросить: «Что будет с counter++ при одновременном выполнении?» Показать разборку инструкции counter++ на чтение-модификацию-запись. Это основа для понимания состязаний.

Обязательно предложить студентам найти ошибки ДО показа ответа. Для решения 1 нарисовать временную диаграмму: оба процесса проверяют флаг другого, видят false, оба устанавливают свой флаг. Для решения 2 — что если процесс 0 завершился? Процесс 1 зависнет навсегда.

Разобрать алгоритм пошагово. Ключевая идея: flag[i]=true показывает «я хочу войти», turn=j показывает «но уступаю тебе». Задать вопрос: «Почему процесс не может одновременно войти в критическую секцию?» Доказательство корректности можно предложить в качестве домашнего задания.

Подчеркнуть, что cli/sti — привилегированные инструкции, доступны только ядру. На многоядерных системах они не помогают — другой ядро продолжит выполнение. Test-And-Set реализуется аппаратно как неделимая операция — на уровне шины с блокировкой (LOCK prefix на x86). Упомянуть CMPXCHG как основу CAS (compare-and-swap).

Важно различать мьютекс и семафор: мьютекс владеет один поток и только он может его отпустить; семафор может захватить один поток, а освободить — другой. Предупредить об ошибке: забыл unlock — дедлок. Упомянуть, что в pthreads есть trylock и timedlock.

Привести реальные примеры: принтер (производитель — приложения, потребитель — драйвер), очередь сообщений, конвейер в ОС. Задать вопрос: «Что будет, если производителей больше, чем потребителей?» Обратить внимание на кольцевой буфер — in и out обойдут границы.

Предложить студентам найти ошибку. Спросить: «Может ли count стать отрицательным?» Показать сценарий: оба процесса одновременно проверяют count и оба проходят проверку. Также отметить busy-waiting — процессор тратится впустую. Это подводит к семафорному решению.

ВАЖНО: порядок sem_wait имеет значение! Если поменять mutex и empty — возможен дедлок. Объяснить почему: процесс захватывает mutex, затем ждёт empty, но потребитель не может уменьшить full, потому что mutex занят. Задать вопрос студентам про порядок sem_post — имеет ли он значение? (Нет, но лучше сначала освободить mutex.)

Монитор автоматически обеспечивает взаимное исключение — студентам не нужно явно управлять блокировками. Сравнить с семафорным решением: код проще, но монитор доступен не во всех языках (Java synchronized — ближайший аналог). Упомянуть, что Java реализует мониторы через wait/notify/notifyAll.

Первый читатель блокирует писателя (wrt), последний читатель разблокирует. Проблема приоритета читателей: писатель может «голодать», если читатели приходят постоянно. Для приоритета писателей нужен более сложный механизм с дополнительным семафором на входе читателей.

Иерархия ресурсов — самый простой способ предотвращения дедлока. Каждый философ нумерует вилки и берёт младшую первой. Альтернативы: 1) ограничить число одновременно сидящих философов (семафор на 4), 2) философ берёт обе вилки атомарно (арбитр), 3) нечётные берут сначала левую, чётные — правую.

Три семафора/мьютекса: customers — будит парикмахера, barber — клиент ждёт пока парикмахер освободится, mutex — защита waiting. Ключевой момент: проверка waiting < CHAIRS должна быть под мьютексом, иначе два клиента могут занять одно «место».

Пробежаться по каждому пункту, задавая студентам вопросы для проверки понимания. Особый акцент на три условия Дейкстры и порядок захвата семафоров в producers-consumers.

Предложить студентам ответить на вопросы устно. Наиболее сложные — вопросы 3, 4 и 5. Если остаются вопросы по алгоритму Петерсона, повторить доказательство на доске.

Задание 4 — хорошее введение: запустить два потока, каждый увеличивает счётчик на миллион, сравнить ожидаемый результат с фактическим. Задания 1 и 3 — основная работа. Задание 2 — повторение IPC. Рекомендовать использовать pthreads и sem_t.